package 算法;

import java.util.Arrays;

/**
 * O(m+n)
 */
public class merge {
    /**
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1,int m,int[] nums2,int n){
        for (int i=0;i<n;++i){
            nums1[m+i]=nums2[i];
        }
        Arrays.sort(nums1);
    }

    /**
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     * O(m+n)
     */
    public int[] merge2(int[] nums1,int m,int[] nums2,int n){
        int k=m+n;
        int[] temp=new int[k];
        for (int index=0,nums1Index=0,nums2Index=0;index<k;index++){
            if(nums1Index>=m){
                temp[index]=nums2[nums2Index++];
            }else if(nums2Index>=n){
                temp[index]=nums1[nums1Index++];
            }else if(nums1[nums1Index]<nums2[nums2Index]){
                temp[index]=nums1[nums1Index++];
            }else{
                temp[index]=nums2[nums2Index++];
            }
        }
        return temp;
    }
}
